package Offer52;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 23737
 * @time 2021.9.14
 * 两个链表的第一个公共结点：
 * 输入两个链表，找出它们的第一个公共节点。
 */
public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(8);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode listNodeB1 = new ListNode(5);
        ListNode listNodeB2 = new ListNode(0);
        ListNode listNodeB3 = new ListNode(1);
        ListNode listNodeB4 = new ListNode(8);
        ListNode listNodeB5 = new ListNode(4);
        ListNode listNodeB6 = new ListNode(5);
        listNodeB1.next = listNodeB2;
        listNodeB2.next = listNodeB3;
        listNodeB3.next = listNodeB4;
        listNodeB4.next = listNodeB5;
        listNodeB5.next = listNodeB6;

        System.out.println(new Solution().getIntersectionNode(listNode1,listNodeB1));
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/*用的链表来进行存储和判断，但是只能过一半*/
class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        //建一个hash表来进行存储
//        HashMap<String,Integer> hashMap = new HashMap<>();
        //建一个链表来存储
        ArrayList<ListNode> objects = new ArrayList<>();
        if (headA != null) {
            objects.add(headA);
            if (headA.next != null) {
                objects.add(headA.next);
            }
        }
        for (int i = 0; i < objects.size(); i++) {
            if ((objects.get(i) == headB) && (objects.get(i+1) == headB.next)){
                return headB;
            }
        }
        return null;
    }
}

/*浪漫相遇（双指针法）*/
class SolutionTwo {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode n1 = headA;
        ListNode n2 = headB;

        while(n1 != n2){
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }
}

/*使用哈希表来进行求解*/
class SolutionThree {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        //建一个哈希表来进行存储
        Set<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while (temp != null) {
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (set.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}


